package com.vincent.algorithms.sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 *
 * 基数排序：按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
 * 有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
 * 基数排序基于分别排序，分别收集，所以是稳定的。
 *
 * 最佳情况时间复杂度：T(n) = O(n * k) k为位数
 * 最差情况：T(n) = O(n * k)
 * 平均情况：T(n) = O(n * k)
 * 稳定性：稳定
 *
 * 基数排序有两种方法：
 * MSD 从高位开始进行排序
 * LSD 从低位开始进行排序
 *
 * 这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
 * 基数排序：根据键值的每位数字来分配桶
 * 计数排序：每个桶只存储单一键值
 * 桶排序：每个桶存储一定范围的数值
 *
 * Created by yangwenchang on 2017/8/25.
 */
public class RadixSort {

    public static void sort(int[] arr) {
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<ArrayList<Integer>>(10);

        for (int i=0;i<10;i++){
            arrayLists.add(new ArrayList<Integer>());
        }

        for (int m = 10; m <= 100; m = m * 10) {
            for (int i = 0; i < arr.length; i++) {
                int val = (arr[i] /(m/10))% m;
                ArrayList list = arrayLists.get(val);
                if (list == null) {
                    list = new ArrayList<Integer>(arr.length / 5);
                    arrayLists.add(i, list);
                }
                list.add(arr[i]);
            }
            int k = 0;
            for (int i = 0; i < 10; i++) {
                ArrayList<Integer> list = arrayLists.get(i);
                if (list != null && list.size() > 0) {
                    while (list.size()>0){
                        arr[k++] = list.remove(0);;
                    }
                }
            }
            System.out.println(arrayLists.toString());
        }
    }

    public static void main(String[] args) {
        int[] arr = {15,6,14,28,90,90,39};
        System.out.println(Arrays.toString(arr));
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

}
